package 简单.贪心思想;

/**
 * 假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种
 * 植在相邻的地块上，它们会争夺水源，两者都会死去。
 * <p>
 * 给你一个整数数组  flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示
 * 没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下
 * 种入 n 朵花？能则返回 true ，不能则返回 false。
 * <p>
 * 来源：https://leetcode-cn.com/problems/can-place-flowers/
 */
public class 种花问题_605 {

    public static void main(String[] args) {
        int[] flowerbed = {1, 0, 0, 0, 1, 0, 0};
        System.out.println(canPlaceFlowers(flowerbed, 2));
    }

    //求最多能种多少朵花，是否大于n
    //判断该位置是否可以种植，需要判断前面和后面是否已经种了花
    public static boolean canPlaceFlowers(int[] flowerbed, int n) {
        int count = 0;
        //花坛只有一个位置时
        if (flowerbed.length == 1 && flowerbed[0] == 0) {
            return 1 >= n;
        } else if (flowerbed.length == 1 && flowerbed[0] == 1) {
            return 0 >= n;
        }
        for (int i = 0; i < flowerbed.length; i++) {
            //判断花坛空闲的位置
            if (flowerbed[i] == 0) {
                //判断花坛的第一个位置
                if (i == 0 && flowerbed[i + 1] == 0) {
                    count++;
                    flowerbed[i] = 1;
                }
                //判断花坛的中间位置
                if (0 < i && i < flowerbed.length - 1 && flowerbed[i - 1] == 0 && flowerbed[i + 1] == 0) {
                    count++;
                    flowerbed[i] = 1;
                }
                //判断花坛的最后一个位置
                if (i == flowerbed.length - 1 && flowerbed[i - 1] == 0) {
                    count++;
                    flowerbed[i] = 1;
                }
            }
        }
        return count >= n;
    }

    //优化，只要count达到要求的n朵直接返回true
    public static boolean efficientCanPlaceFlowers(int[] flowerbed, int n) {
        int count = 0;
        //花坛只有一个位置时
        if (flowerbed.length == 1 && flowerbed[0] == 0) {
            return 1 >= n;
        } else if (flowerbed.length == 1 && flowerbed[0] == 1) {
            return 0 >= n;
        }
        for (int i = 0; i < flowerbed.length; i++) {
            //判断花坛空闲的位置
            if (flowerbed[i] == 0) {
                //判断花坛的第一个位置
                if (i == 0 && flowerbed[i + 1] == 0) {
                    count++;
                    flowerbed[i] = 1;
                }
                //判断花坛的中间位置
                if (0 < i && i < flowerbed.length - 1 && flowerbed[i - 1] == 0 && flowerbed[i + 1] == 0) {
                    count++;
                    flowerbed[i] = 1;
                }
                //判断花坛的最后一个位置
                if (i == flowerbed.length - 1 && flowerbed[i - 1] == 0) {
                    count++;
                    flowerbed[i] = 1;
                }
            }
            //满足条件直接返回
            if (count >= n) {
                return true;
            }
        }
        return count >= n;
    }
}
